Thanks to recent advances, AI Planning has become the underlying techniquefor several applications. Figuring prominently among these is automated WebService Composition (WSC) at the "capability" level, where services aredescribed in terms of preconditions and effects over ontological concepts. Akey issue in addressing WSC as planning is that ontologies are not only formalvocabularies; they also axiomatize the possible relationships between concepts.Such axioms correspond to what has been termed "integrity constraints" in theactions and change literature, and applying a web service is essentially abelief update operation. The reasoning required for belief update is known tobe harder than reasoning in the ontology itself. The support for belief updateis severely limited in current planning tools. Our first contribution consists in identifying an interesting special case ofWSC which is both significant and more tractable. The special case, which weterm "forward effects", is characterized by the fact that every ramification ofa web service application involves at least one new constant generated asoutput by the web service. We show that, in this setting, the reasoningrequired for belief update simplifies to standard reasoning in the ontologyitself. This relates to, and extends, current notions of "message-based" WSC,where the need for belief update is removed by a strong (often implicit orinformal) assumption of "locality" of the individual messages. We clarify thecomputational properties of the forward effects case, and point out a strongrelation to standard notions of planning under uncertainty, suggesting thateffective tools for the latter can be successfully adapted to address theformer. Furthermore, we identify a significant sub-case, named "strictly forwardeffects", where an actual compilation into planning under uncertainty exists.This enables us to exploit off-the-shelf planning tools to solve message-basedWSC in a general form that involves powerful ontologies, and requires reasoningabout partial matches between concepts. We provide empirical evidence that thisapproach may be quite effective, using Conformant-FF as the underlying planner.
展开▼
